Communications systems such as packet switched networks allow devices to transmit and receive information. Referring now to FIG. 1A, a conventional packet switched network is shown. Each conventional device 10, 12, 16, 18 can act as both a sending site and a receiving site to send and receive data from the other devices 10, 12, 16, 18 in the network. Conventional router 14 receives data in the form of packets from each sending device 10, 12, 16, 18 and routes it to the proper receiving device 10, 12, 16, 18 according to header information contained in the packet.
Header information may contain an identifier containing routing information and a "nearly unique" packet number in addition to other information. The nearly unique packet number may be an identifier which has a large number of bits randomly or sequentially selected by the sending site, making the identifier also nearly unique. Although the identifier is unlikely to be the same as the identifier of the header from another packet sent to the router 14 at the same time, there is a small probability that two headers being sent to the router 14 could have the same identifier.
Referring now to FIG. 1B, a conventional packet 102 is shown. Header 110 is followed by a number of words of data 112, 114, 116 in a certain order. The header 110 in FIG. 1B has an identifier 130 in bits 80 through 115, though other sizes and bit positions of identifiers are possible. The identifier 130 contains "nearly unique" information Each data word 112, 114, 116 and the header 110 has an appended error code 120, 122, 124, 126, which can be used to detect and even correct errors in the remainder of the individual words of data 112, 114, 116 or header 110 information. For example, each word 110, 112, 114, 116 in the packet 102 may contain 128 bits of data or header information and an 8 bit error code 120, 122, 124, 126 to create 136 bit words for transmission at a sending site. The error codes 120, 122, 124, 126 are checked against the data 170 at the receiving site to detect or correct errors within the data portion 170 of each word 110, 112, 114, 116. Once the data is determined to be correct, the error codes 120, 122, 124, 126 may be removed from the data portions 170 by the receiving site, and the data portions 170 of each word 110, 112, 114, 116 are ready for use by the receiving site.
Conventional error detection and error detection and correction codes may detect and correct errors related to a single word of a digital transmission. Many methods may be used to implement various error detection codes and error detection and correction codes. The methods described in Rao T. R. N. & E Fujiwara, Error-Control Coding for Computer Systems (Prentice Hall, 1989), D. K. Pradhan & J. J. Stiffler, Error-Correcting Codes and Self Checking Circuits, 27-37 (Computer, Vol 13 No.3 March, 1980), H. Imai Essentials of Error-Control-Coding Techniques (Academic Press, 1990) or E. Fujiwara et. al Error-Control Coding in Computers, 63-72 (Computer July 1990) may be used to detect certain errors within the data portion of a word 110, 112, 114, 116.
Error codes 120, 122, 124, 126 may be generated using a binary matrix multiplication process which multiplies the data portion 170 of a word 110, 112, 114, 116 with a matrix which is predefined by the designer of the error code. For example, error codes set forth above are generated by binary matrix multiplication of the data portion 170 of each word 110, 112, 114, 116 and the matrix set forth in Appendix A. Each binary matrix product of the matrix of Appendix A and each word 110, 112, 114, 116 is the error code portion 120, 122, 124, 126, respectively to be appended to the data portion 170 of the word 110, 112, 114, 116.
Binary matrix multiplication works as follows:
Assume two matrices, A and B: ##EQU1##
A.times.B using binary matrix multiplication produces the m bit result, EQU C=c.sub.1 c.sub.2 c.sub.3 . . . c.sub.m (Eq. 2)
Where ##EQU2## and where the "product" (indicated by `x`) of two numbers is the binary "AND" function, and the "sum" of a sequence of numbers is the exclusive-OR of the sequence: 0 if the number of `1`s in the sequence is an even number, and 1 otherwise.
Each of the products in Equation 3 need not be computed where a.sub.j or b.sub.ji is known in advance to be zero, because the product of these terms will not affect the result c.sub.i. Additionally, where the terms of one matrix are known in advance to be zero or one, the product itself need not be computed: the corresponding terms in the other matrix which would have been ANDed with the known terms equal to one may be exclusive-ORed with each other. Thus Equation 3a becomes, for known values of b.sub.ji : ##EQU3##
While conventional error detection and error detection codes can detect, or detect and correct, certain errors within each word 110, 112, 114, 116 of a packet 102, these conventional error detection codes and error detection and correction codes cannot detect the presence of intraword errors, such as a word in the packet 102 out of its original sequence or a word from one packet improperly inserted in place of a word in another packet.
The first of the two problems arises when words 110, 112, 114, 116 are assembled, transmitted or received in the improper order. Because the data portion 170 within each word 110, 112, 114, 116 may match the corresponding error detection or error detection and correction codes 120, 122, 124, 126 the error detection or error detection and correction code 120, 122, 124, 126 cannot be used to identify the out-of-sequence error. The second problem arises when a word which is located in another packet is inserted among the words 110, 112, 114, 116 of the first packet. This problem may arise if a word is not properly written into a memory, and an old value remains in place of the new value. Because the data portion 170 in this improperly-inserted word can match the corresponding error code, using an error correction and detection code will not identify the fact that the word has been improperly inserted into the wrong packet. Thus, other means of detecting these additional two errors are required.
One method which identifies missing or improperly inserted words is to use a checksum technique. A transmitting site adds a final checksum word 118 which may contain a parity, either odd or even, of each of the columns from words 110, 112, 114, 116 above the checksum 118. For example, parity in column 0 is determined by exclusive-ORing the bits in Column 0 of words 110, 112, 114, 116. Upon receipt of the packet, the bits in each column are tested to ensure the proper parity. Improperly inserted words or missing words may generate parity errors. Checksum 118 may also be a cyclical redundancy checksum, or CRC. However, the use of a checksum 118 requires that all of the words 110, 112, 114, 116, 118 are received before errors may be detected. Where words are received sequentially, undesirable delays are introduced before each word 110, 112, 114, 116 may be used at the receiving site. Additionally, the checksum method cannot identify a packet in which each of the words 110, 112, 114, 116 is in the packet, but out of their original order.